#include <iostream>

using namespace std;

struct BinaryTreeNode{

    int value;
    BinaryTreeNode * left;
    BinaryTreeNode * right;
};


BinaryTreeNode* CreateBinaryTreeNode(double dbValue)
{
    BinaryTreeNode* pNode = new BinaryTreeNode();
    pNode->value = dbValue;
    pNode->left = nullptr;
    pNode->right = nullptr;

    return pNode;
}

void ConnectTreeNodes(BinaryTreeNode* pParent, BinaryTreeNode* pLeft, BinaryTreeNode* pRight)
{
    if(pParent != nullptr)
    {
        pParent->left = pLeft;
        pParent->right = pRight;
    }
}


bool Equals(double k1, double k2){
    if ( (k1-k2>-0.00000001) && (k1-k2<0.00000001)){
        return true;
    }else {
        return  false;
    }
}

// 判断整个子树的全部节点是否与大树节点相同
bool DoesTree1HadTree2(BinaryTreeNode * root, BinaryTreeNode * subRoot){
    if ( subRoot == nullptr )
        return true;

    if ( root == nullptr )
        return false;
    
    // 判断值是否相同
    if ( root->value != subRoot->value){
        return false;
    } 
    return DoesTree1HadTree2(root->left, subRoot->left) && DoesTree1HadTree2(root->right, subRoot->right);
}

bool substructureInTree(BinaryTreeNode * root , BinaryTreeNode * subRoot){
    bool flag = false;

    if ( root != nullptr && subRoot != nullptr ){
        // 判断根是否相同
        if ( root->value == subRoot-> value){
            // 相等
            flag = DoesTree1HadTree2(root, subRoot);
        }
            // 不相等
            if (!flag) flag = substructureInTree(root->left, subRoot);
            if (!flag) flag = substructureInTree(root->right, subRoot);
       
    }
    return flag;
}

int main(void){
    BinaryTreeNode* pNodeA1 = CreateBinaryTreeNode(8);
    BinaryTreeNode* pNodeA2 = CreateBinaryTreeNode(8);
    BinaryTreeNode* pNodeA3 = CreateBinaryTreeNode(7);
    BinaryTreeNode* pNodeA4 = CreateBinaryTreeNode(9);
    BinaryTreeNode* pNodeA5 = CreateBinaryTreeNode(2);
    BinaryTreeNode* pNodeA6 = CreateBinaryTreeNode(4);
    BinaryTreeNode* pNodeA7 = CreateBinaryTreeNode(7);

    ConnectTreeNodes(pNodeA1, pNodeA2, pNodeA3);
    ConnectTreeNodes(pNodeA2, pNodeA4, pNodeA5);
    ConnectTreeNodes(pNodeA5, pNodeA6, pNodeA7);

    BinaryTreeNode* pNodeB1 = CreateBinaryTreeNode(8);
    BinaryTreeNode* pNodeB2 = CreateBinaryTreeNode(9);
    BinaryTreeNode* pNodeB3 = CreateBinaryTreeNode(2);

    ConnectTreeNodes(pNodeB1, pNodeB2, pNodeB3);

    bool result = substructureInTree(pNodeA1, pNodeB1);
    cout << "result : " << result << endl;
    return 0;
}